When the cost of reproduction for males and variance in female quality are high, males are predicted to show adaptive mate choice. Using Drosophila melanogaster, we test this prediction and show that sperm limited males preferentially mated with young and/or well fed females. The preferred females had higher reproductive output – direct evidence of adaptive precopulatory male mate choice. Our most striking finding is the strong positive correlation between the degree of mating bias showed by the males and the variance in the fitness of the females. We discuss the possible mechanism for such adaptive male mate choice and propose that such choice has important consequences with respect to the existing understanding of the mating system and the evolution of aging.